This invention relates to information processing systems, and more particularly to buffering data between main memory and the processing elements in such systems. Even more particularly this invention relates to means for prefetching vector and array data, which is being accessed according to a fixed pattern and/or within a relatively small locality, from a data store, such as main memory, into a processing element.
Any processing element must receive the data it is to operate on from some form of data store. Ideally, this data would always be instantly available whenever it is needed by the processing element so that the processing element would never have to wait for data to be fetched. In slower processing systems, the data store is main memory since the main memory is fast enough to keep up with the slower processors. As processor speed increases relative to main memory speed, processors spend a significant amount of time waiting for data unless some form of high speed intermediate memory is placed between the main memory and the processor. This waiting time can be reduced by using a very fast technology to construct the intermediate memory. The difference in the speeds of the main memory and processing element is accommodated by the intermediate memory because the processing element tends to use data and intermediate results more than once.
The waiting time can be further reduced by anticipating which data is to be needed, prefetching it from main memory, and then making the data that is needed next immediately available to the processing element. The needed data is more easily anticipated when accessing vectors and arrays in some regular manner. Most numerical techniques follow a regular pattern when accessing vectors and arrays and, at any given time, must access data confined to a small locality. This invention is designed to take advantage of this method of accessing vectors and arrays.
The conventional means of providing an intermediate data memory is to use a data cache such as those discussed by Harold Stone in High-performance Computer Architecture, Addison-Wesley, 1987, pp. 29-74. These caches are widely used, but they do not anticipate which data is needed from main memory. Instead, they retrieve the data from main memory when it is requested by the processing element and retain the data and any intermediate results produced from the data so that they can be reused without further accesses to the main memory. Therefore, there is considerable waiting when the data is originally fetched. Also, these caches are not designed to make data immediately available to the processing element; the cache accesses are limited by the speed of the cache memory.